NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/6342

Text File | 1996-08-05 | 1.7 KB | 41 lines

Path: sun001.spd.dsccc.com!spd!jmccarty
From: [e-mail] (Mike McCarty)
Newsgroups: comp.lang.c
Subject: Re: merge algorithm
Date: 23 Feb 1996 23:50:13 GMT
Organization: DSC Communications Corporation, Plano, Texas USA
Message-ID: <4gljrl$[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: aplo139.spd.dsccc.com

In article <[e-mail]>,
Joe E. Coffland <[e-mail]> wrote:
)I am trying to find an algorithm to merge two sorted arrays containing
)n elements.
)ie. A[1] <= A[2]<= ... <= A[m] and A[m+1] <= A[m+2] <= ... <A[n]
)The algorithm must run in O(n) time and require only a small amount of
)fixed additional memory regardless of the size of m or n. I have reason
)to believe that there is such an algorithm but I have only been able to
)find algorithms that meet the memory restriction but run in at best
)O(nlogn) and are recursive (which can through some work of course be
)changed in to an iterative algorithm). If any one can point me to a book
)or any other source of information on the subject or just get me headed
)in the right direction it would be greatly appriciated.
)
)Thank you in advance,
)Joe Coffland
)please mail to: [e-mail]


Won't a simple exchange algorithm work? Start with pointers into the
left and right halves. Advance the left pointer until you find an
element larger than the right pointer data. Exchange the left pointer
data with the right pointer data. Advance the left pointer etc. When you
have gone through the entire data set, there is only one output array.

Mike
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

I don't speak for DSC.         <- They make me say that.